package com.tucc.hello.leetcode.no1_400.no1_200.no1_20.no11_20.no18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> resultList = solution.fourSum(nums, target);
        resultList.forEach(result -> {
            result.stream().map(o -> o + " ").forEach(System.out::print);
            System.out.println();
        });
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        Arrays.sort(nums);
        listSum(nums, 0, 4, new ArrayList<>(), 0, target, resultList);
        return resultList;
    }

    public void listSum(int[] nums, int ci, int n, List<Integer> result, int cSum, int target,
                        List<List<Integer>> resultList) {
        if (n == result.size()) {
            if (cSum == target) {
                resultList.add(new ArrayList<>(result));
            }

        } else {
            int next = ci;
            int size = result.size();
            while (next < nums.length) {
                if(nums.length - next < n - result.size()){
                    break;
                }
                int nextVal = nums[next];
                if(nextVal < 0 || (cSum + nextVal <= target)) {
                    result.add(nextVal);
                    cSum += nextVal;
                    listSum(nums, ++next, n, result, cSum, target, resultList);
                    result.remove(size);
                    cSum -= nextVal;
                    while(next < nums.length && nums[next] == nums[next - 1]){
                        next ++;
                    }
                }
                else {
                    break;
                }
            }

        }
    }
}
